


		GALBENI - SOLUTIE
	       -------------------

	Presupunem ca avem o solutie a problemei (configuratia A0,B0,C0 am transfor-
mat-o in configuratia Ak,Bk,Ck cu Ak=Bk). Mai aplicam o operatie, folosind cele 2
gramezi egale (Ak,Bk=Ak,Ck) si obtinem 2*Ak,0,Ck). Deci problema se poate reformula,
cerandu-se sa se obtina 0 intr-o gramada (inainte de ultima operatie de scadere aveam
2 gramezi identice).
	Vom cauta un sir de operatii (Ai,Bi,Ci -> Ak,Bk,Ck cu k>i) astfel incat
min(Ai,Bi,Ci)>min(Ak,Bk,Ck). Cum Ai,Bi,Ci sunt numere naturale si nu exista siruri
descrescatoare infinte de numere naturale, minimul sumelor din cele trei gramezi va
ajunge intr-un numar finit de pasi la 0.
	Fie configuratia Ai,Bi,Ci. Presupunem ca Ai<=Bi<=Ci (deci, min(Ai,Bi,Ci)=Ai).
Vom transforma configuratia intr-o configuratia Ak,Bk,Ck cu Bk=rest[Bi/Ai]. Evident
Bk<Ai, deci Bk<min(Ai,Bi,Ci) si min(Ak,Bk,Ck)<min(Ai,Bi,Ci). Pentru aceasta transfor-
mare, vom calcula x=[Bi/Ai]. Analizam bitii reprezentarii in baza 2 a lui x pornind de
la cel mai putin semnificativ. Pentru un bit de 0 trebuie sa nu modificam Bi, dar sa
deplasam la stanga bitii Ai cu o pozitie. Aceasta se realizeaza simplu printr-o trans-
formare de forma Ai,Bi,Ci -> Ai*2,Bi,Ci-Ai.
	Este evident ca dupa ce am parcurs toti bitii lui x, in gramada B vom avea
rest[Bi/Ai] galbeni. Trebuie sa ne asiguram ca aceste transformari nu genereaza numere
negative de galbeni. Este evident ca Ak>0 (A se dubleaza la fiecare operatie) si Bk>=0
(B scade la fiecare operatie, dar valoarea minima este rest[Bi/Ai]>=0). Sirul Ck este
de asemenea descrescator, deci va trebuie sa calculam valoarea sa minima. Observam ca
Ai+Bi+Ci=Ak+Bk+Ck. Dar Bk=rest[Bi/Ai]. Deci Ai+(Bk+Ai*x)+Ci=Ak+Bk+Ck si, scazand Bk din
ambii membri, avem: Ai*(1+x)+Ci=Ak+Ck. Pentru fiecare bit al lui x, Ai isi dubleaza va-
loarea, deci Ak<=Ai*x*2. Dar,Ck=Ci+Ai*(1+x)-Ak, deci Ck>=Ci+Ai*(1+x)-Ai*x*2, adica Ck>=
Ci-Ai*(x-1). Dar, Bi>=Ai*x, deci Ci>=Ai*x. Rezulta ca Ck>=Ai, deci Ck>=0. In concluzie
aceste transformari sunt valide si problema poate fi rezolvata, folosind acest algoritm.
	O estimare a complexitatii indica ordinul O(k*logN), unde N=max(A0,B0,C0) si k
este valoarea minima pentru care F(k)>=N (F este sirul lui Fibonacci). Folosind un re-
zultat datorat lui A.Moivre, ajungem la k=O(logN). Deci algoritmul are complexitatea
O((logN)^2).